In a heterogeneous network, each network element, or node, may support one or more protocol sets. For example, a network element may support OSI (Open System Interconnect) protocols anchor IP (Internet protocols) protocols. In order that one network element may communicate with another network element, they must support at least one protocol set in common since different protocol sets do not interoperate. It is possible to send data packets, or traffic, conforming with one protocol set to a destination via one or more network elements that do not support the protocol set of the data by means of data tunnelling. Data tunnelling involves the encapsulation of one protocol set within another protocol set. For example, assume that it is desired to send IP data packets from a source network element that supports IP protocols to a destination network element that also supports IP protocols via a sub-network comprising network elements that only support OSI protocols. The IP data packets are encapsulated within OSI protocols for their passage through the OSI-only network elements and de-encapsulated afterwards. In order that data tunnelling may be achieved, at least some of the network elements between the source and the destination must be able to support both protocol sets. Such network elements are said to be bi-lingual.
PCT/EP01/14203, a copy of which is filed herewith, and which is incorporated by reference, discloses an autotunnelling scheme in a heterogeneous network in which bi-lingual network elements are arranged to create automatically and dynamically data tunnels in order to forward traffic across a heterogeneous network.
In order to learn about the network around it, and to calculate paths across the network to destination nodes, a network element usually runs a routing algorithm. Typically, the calculation of the routing algorithm is a computationally intensive operation and accounts for a significant proportion of the network elements processing time. The compilation of information concerning nearest bi-lingual network elements, as required by the aforementioned auto-tunnelling scheme, must be performed in addition to the normal tasks of the routing algorithm. U.S. patent application Ser. Nos. 10/039,432 and 10/032,417 disclose how such topology information can be efficiently compiled in order to reduce the computational burden and so improve the speed of operation of the network element.
It will be understood that the term “protocol” as used herein is intended to embrace protocol set, or protocol stack, where the set (or stack) may comprise one or more protocols. For example, OSI and IP may each be considered to comprise a respective set of protocols, but may be referred to herein as OSI protocol or IP protocol respectively.
The present invention relates particularly, but not exclusively, to OSI and IP protocols, and respective ISO (International Organisation for Standardisation) and IETF (Internet Engineering Task Force) standard describing these protocols may be obtained from the Internet.
A network element supports one or more routing protocols in order to route data traffic across a network. Integrated IS-IS (Intermediate System to Intermediate System) is a routing protocol that was devised as an extension to IS-IS routing protocol and, in conjunction with data tunnelling, allows network elements to route IP traffic as well as OSI traffic. Integrated IS-IS is described in IETF standard RFC 1195 IS-IS is described in ISO 10589.
IS-IS and Integrated IS-IS normally employ a routing algorithm know as SPF (Shortest Path First) in order to calculate the “shortest” path across a network from one node to another RFC 1195 and ISO 10589 are hereby incorporated herein by way of reference.
OSI traffic comprises OSI data packets, where OSI data packets conform with OSI protocol, particularly CLNP (ConnectionLess mode Network Protocol), CLNP being an OSI network layer protocol. CLNP is the name given to the type of data packets or PDUs (Protocol Data Units) that are used to provide CLNS (ConnectionLess mode Network Service). CLNS is the service provided by the network layer of an OSI protocol stack to higher layers of the stack. Provision of CLNS service results in CLNP packets or PDUs being passed to lower layers of the stack.
IP traffic comprises IP data packets, where IP data packets conform with IP protocol, particularly IPv4 and IPv6 which are IP network layer protocols.
An IP-only network element, or node, is a node that can natively route IP packets but not OSI packets. An OSI-only node is a node that can natively route OSI packets, but not IP packets. A dual, or bilingual, network element, or network node, is a node that can natively route at least two protocols, particularly network layer protocols. This term is used hereinafter particularly to indicate either a node that routes both CLNS/CLNP and IPv4, or alternatively a node that routes both IPv4 and IPv6.
Hereinafter, the term “network node” (or “node”) is used in preference to “network element” to conform with the terminology favoured in International PCT patent application number PCT/EP01/14203, although either term may be used.
It will be understood that the term “router” as used hereinafter is intended to embrace a network element, or network node, (or part thereof) that is arranged to act as a data router. Hence, a “heterogeneous router” is a network node (or part thereof) that is capable of routing at least two protocol sets. It should be noted that the term “heterogeneous router” implies a multi-protocol router and is used here in preference to the term “dual router”, which term is used to imply a multi-protocol router in U.S. patent application Ser. Nos. 10/039,432, and U.S. 10/032,417.
An adjacent network node (“adjacency”) is a reachable neighbouring node. The term “adjacency” is defined in section 3.6.3 of ISO/IEC 10589 and is used herein to denote a reachable neighbouring node. A physical neighbouring node is not necessarily a valid adjacency, since it might be in a different network area or network level. Thus, an adjacency may be maintained between nodes that are not physical neighbours.
U.S. patent application Ser. No. 10/039,432 describes a routing algorithm which determines the encapsulation capability of each router. Advantageously, by providing an indication of encapsulation capability, heterogeneous routers which do not in fact have encapsulation capability despite being able to support both protocols are no longer erroneously selected as termination points for auto-tunnelling. U.S. Ser. No. 10/038,432 describes the indication of the order of encapsulation by using a suitable encapsulation capability identifier to indicate, for example, whether OSI over IP is supported but not IP over OSI.
U.S. Pat. No. 5,251,205 (Callon et al) describes multiple protocol routing in which the Dijkstra algorithm is modified to generate information on how to encapsulate and forward packets through the network. However Callon et al do not consider how to modify the cost d(N) used in the routing algorithm if encapsulation is required to ensure that encapsulation requirements are considered when selecting the optimum path in a heterogeneous network. Nor do Callon et al include an additional field to determine the optimum heterogeneous router to ensure the minimum number of encapsulations occur along that path.
An object of the invention seeks to mitigate and or obviate the aforementioned problems known in the prior art by providing a routing method which calculates an optimum path using the cost of encapsulation. The optimum path is the ‘shortest’ path returned by a modified Dijkstra-type routing algorithm which at least includes the cost of encapsulation when determining the most efficient (in terms of assigned cost) path across a heterogeneous network.
Another object of the invention seeks to provide a method of determining an optimum path across a heterogeneous network which at least uses the cost of encapsulation between protocol sets.